package me.chan.string;

/**
 * Created by JanGin on 2018/4/16.
 */
public class KMP {

    private KMP(){}

    public static int indexOf(String main, String pattern) {

        int[] next = getNext(pattern);

        int i = 0, j = 0;
        while (i < main.length() && j < pattern.length()) {
            if (j == -1 || main.charAt(i) == pattern.charAt(j)) {
                ++i;
                ++j;
            } else {
                j = next[j];
            }
        }

        if (j == pattern.length())
            return i - pattern.length();


        return -1;
    }

    private static int[] getNext(String pattern) {
        int[] next = new int[pattern.length()];
        int i = 0, j = -1;
        next[0] = -1;
        while (i < pattern.length() - 1) {
            if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
        return next;
    }

    public static void main(String[] args) {
        String main = "acabaabaabcacaabc",
                pattern = "abaabcac";

        int index = indexOf(main, pattern);
        System.out.println("模式串在主串首次出现的索引位置是:" + index);
    }
}
